﻿#define _CRT_SECURE_NO_WARNINGS 1
//实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
//bool isUnique(char* astr){
//	int i = 0;
//	int j = 0;
//	int len = strlen(astr);
//	int falg = 0;
//	for (i = 0; i<len; i++)
//	{
//		falg = 1;
//		for (j = 0; j<len; j++)
//		{
//			if (astr[i] == astr[j] && i != j)
//			{
//				falg = 0;
//				break;
//			}
//		}
//		if (falg == 0)
//		{
//			return false;
//		}
//	}
//	return true;
//}








//给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
//
//说明：
//
//你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/single-number
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int singleNumber(int* nums, int numsSize){
//	int count = 0;
//	int i = 0;
//	for (i = 0; i<numsSize; i++)
//	{
//		count ^= nums[i];
//	}
//	return count;
//}








/**给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-array-by-parity-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* Note: The returned array must be malloced, assume caller calls free().
*/
//int* sortArrayByParityII(int* nums, int numsSize, int* returnSize){
//	int i = 0;
//	int* a = (int*)malloc(sizeof(int)*numsSize);
//	int j = 0;
//	int k = 1;
//	*returnSize = numsSize;
//	for (i = 0; i<numsSize; i++)
//	{
//		if (nums[i] % 2 == 1)
//		{
//			a[k] = nums[i];
//			k += 2;
//		}
//		else
//		{
//			a[j] = nums[i];
//			j += 2;
//		}
//	}
//
//	return a;
//}








//符合下列属性的数组 arr 称为 山脉数组 ：
//arr.length >= 3
//存在 i（0 < i < arr.length - 1）使得：
//arr[0] < arr[1] < ... arr[i - 1] < arr[i]
//arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
//给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/peak-index-in-a-mountain-array
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int peakIndexInMountainArray(int* arr, int arrSize){
//	int i = 0;
//	for (i = 1; i<arrSize - 1; i++)
//	{
//		if (arr[i]>arr[i - 1] && arr[i]>arr[i + 1])
//		{
//			return i;
//		}
//	}
//	return i;
//}








//给你两个字符串，请你从这两个字符串中找出最长的特殊序列。
//
//「最长特殊序列」定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。
//
//子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。
//
//输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 - 1。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/longest-uncommon-subsequence-i
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int findLUSlength(char * a, char * b){
//	int len1 = strlen(a);
//	int len2 = strlen(b);
//	if (strcmp(a, b) == 0)
//	{
//		return -1;
//	}
//	return len1>len2 ? len1 : len2;
//}






//爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
//
//最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
//
//选出任一 x，满足 0 < x < N 且 N % x == 0 。
//用 N - x 替换黑板上的数字 N 。
//如果玩家无法执行这些操作，就会输掉游戏。
//
//只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/divisor-game
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool divisorGame(int n){
//	int i = 0;
//	int count = 0;
//	while (n>1)
//	{
//		for (i = 1; i<n; i++)
//		{
//			if (n%i == 0)
//			{
//				count++;
//				n -= i;
//				break;
//			}
//		}
//	}
//	if (count % 2 == 1)
//	{
//		return 1;
//	}
//	else
//	{
//		return 0;
//	}
//}










/**杨辉三角
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
//int** generate(int numRows, int* returnSize, int** returnColumnSizes){
//	*returnSize = numRows;
//	*returnColumnSizes = (int*)malloc(sizeof(int)*numRows);
//	int**a = (int**)malloc(sizeof(int*)*numRows);
//	int i = 0;
//	int j = 0;
//	for (i = 0; i<numRows; i++)
//	{
//		(*returnColumnSizes)[i] = i + 1;
//		a[i] = (int*)malloc(sizeof(int)*(i + 1));
//		for (j = 0; j <= i; j++)
//		{
//			if (j == i || j == 0)
//			{
//				a[i][j] = 1;
//			}
//			else
//			{
//				a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
//			}
//		}
//	}
//	return a;
//}












/**给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。

你可以返回满足此条件的任何数组作为答案
* Note: The returned array must be malloced, assume caller calls free().
*/
//int* sortArrayByParity(int* nums, int numsSize, int* returnSize){
//	int i = 0;
//	int j = numsSize - 1;
//	int k = 0;
//	int*a = (int*)malloc(sizeof(int)*numsSize);
//	while (i <= j)
//	{
//		if (nums[k] % 2 == 0)
//		{
//			a[i] = nums[k];
//			i++;
//		}
//		else
//		{
//			a[j] = nums[k];
//			j--;
//		}
//		k++;
//	}
//	*returnSize = numsSize;
//	return a;
//}








/**给你两个数组，arr1 和 arr2，

arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/relative-sort-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* Note: The returned array must be malloced, assume caller calls free().
*/
//int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize){
//	int arr[1001] = { 0 };
//	int i, j = 0;
//	for (i = 0; i<arr1Size; i++)
//	{
//		arr[arr1[i]]++;
//	}
//	for (i = 0; i<arr2Size; i++)
//	{
//		while (arr[arr2[i]]>0)
//		{
//			arr1[j] = arr2[i];
//			j++;
//			arr[arr2[i]]--;
//		}
//	}
//	for (i = 0; i<1001; i++)
//	{
//		while (arr[i]>0)
//		{
//			arr1[j++] = i;
//			arr[i]--;
//		}
//	}
//	*returnSize = arr1Size;
//	return arr1;
//}







//你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。
//
//你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。
//
//给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。
//int countBalls(int lowLimit, int highLimit){
//	int i = 0;
//	int max = 0;
//	int count = 0;
//	int n = 0;
//	int a[100] = { 0 };
//	for (i = lowLimit; i <= highLimit; i++)
//	{
//		count = 0;
//		n = i;
//		while (n != 0)
//		{
//			count += n % 10;
//			n /= 10;
//		}
//		a[count]++;
//		max = fmax(max, a[count]);
//	}
//	return max;
//}
